package com.tgy.algorithm._经典题目01;

/**
 * 括号有效配对是指
 * 1)任何一个左括号都能找到和其正确配对的右括号2)任何一个右括号都能找到和其正确配对的左括号
 * 有效的(()) ()() (()()) 等
 * 无效的(())( 等
 * 问题一怎么判断一个括号字符串有效?
 * 问题二如果一个括号字符串无效，返回至少填几个字符能让其整体有效
 */
public class _002_括号有效配 {

    public static boolean isValide(String content) {

        if (content == null || content.length() == 0 || content.length() == 1) {
            return false;
        }

        int len = content.length();

        int count = 0;
        int index = 0;
        char[] chars = content.toCharArray();
        while (index < len) {

            char aChar = chars[index++];
            if (aChar == '(') {
                count++;
            }else {
                count--;
            }

            if (index < 0) {
                return false;
            }
        }

        return count == 0;
    }

    public static int addBracket(String content) {

        if (content == null || content.length() == 0) {
            return 0;
        }

        int index = 0;
        int count = 0;
        int addCount = 0;

        int len = content.length();
        char[] chars = content.toCharArray();

        while (index < len) {
            char aChar = chars[index++];
            if (aChar == '(') {
                count++;
            }else {
                count--;
            }

            if (count < 0 ) {
                addCount -= count;
                count = 0;
            }
        }

        return addCount + count;
    }

    public static void main(String[] args) {

//        boolean valide = isValide("(())())()(()())");
//        System.out.println(valide);
        int added = addBracket(")))(((");
        System.out.println(added);
    }
}
